package com.gxc.rapacity;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 中位数
 * 利用大跟堆和小跟堆两个堆
 */
public class Median {

    public static void main(String[] args) {
        int[] a = {7, 4 ,3,6};

        int num = median(a);
        System.out.println(num);

        int[] b = {5, 4 ,3,6,7};
        num = median(b);
        System.out.println(num);
    }

    private static int median(int[] a) {
        PriorityQueue<Integer> small = new PriorityQueue<>();
        PriorityQueue<Integer> big = new PriorityQueue<>(new BigComparator());

        big.add(a[0]);
        for (int i = 1; i < a.length; i++) {
            if (a[i]>big.peek()) {
                small.add(a[i]);
            } else {
                big.add(a[i]);
            }
            //当两个堆的大小差等于2，调整堆大小，从多的往少的移动
            if (Math.abs(big.size() - small.size())>1) {
                if (big.size() > small.size()) {
                    small.add(big.poll());
                } else {
                    big.add(small.poll());
                }
            }
        }

        if (a.length%2==0) {
            return big.peek()+(small.peek()-big.peek())/2;
        } else {
            if (big.size() > small.size()) {
                return big.peek();
            } else {
                return small.peek();
            }
        }
    }

    public static class BigComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }

}
